Ćwiczenia/1. Ćwiczenia/Zadanie 6. (wyszukiwanie binarne).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Proszę zaimplementować funkcję, która otrzymuje na wejściu posortowaną niemalejąco tablicę A o rozmiarze n oraz liczbę x i sprawdza, czy x występuje w A. Jeśli tak, to zwraca najmniejszy indeks, pod którym x występuje."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_first(arr, val):\n",
    "    i = 0\n",
    "    j = len(arr) - 1\n",
    "    while i <= j:\n",
    "        center_idx = (i + j) // 2\n",
    "        if val > arr[center_idx]:\n",
    "            i = center_idx + 1\n",
    "        else:\n",
    "            j = center_idx - 1\n",
    "    return i if i < len(arr) and arr[i] == val else None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Implementacja funkcji testującej prawidłowość algorytmu (nie jest częścią zadania)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def test_find(fn, *, reps=20):\n",
    "    passed = 0\n",
    "    for i in range(reps):\n",
    "        values = sorted(random.randint(-10, 10) for _ in range(random.randint(5, 25)))\n",
    "        searched = random.randint(-10, 10)\n",
    "        result = fn(values, searched)\n",
    "        try:\n",
    "            expected = values.index(searched)\n",
    "        except ValueError:\n",
    "            expected = None\n",
    "        is_correct = expected == result\n",
    "        passed += is_correct\n",
    "        print(f'#{i+1} Test (already passed: {passed}/{reps})')\n",
    "        print('Values:', values)\n",
    "        print('Searched value:', searched)\n",
    "        print('Expected:', expected)\n",
    "        print('Result:', result)\n",
    "        print(f'Test {\"passed\" if is_correct else \"failed\"}')\n",
    "        print()\n",
    "    print(f'Total passed: {passed}/{reps}')\n",
    "    print(f'An algorithm is {\"correct\" if passed == reps else \"wrong\"}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Przykładowy test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#1 Test (already passed: 1/100)\n",
      "Values: [-9, -9, -7, -7, -6, -5, -2, -1, 0, 1, 3, 4, 5, 8]\n",
      "Searched value: 3\n",
      "Expected: 10\n",
      "Result: 10\n",
      "Test passed\n",
      "\n",
      "#2 Test (already passed: 2/100)\n",
      "Values: [-10, -9, -8, -7, -7, -6, -5, -4, -3, -1, 0, 1, 7, 7, 8, 10, 10]\n",
      "Searched value: 6\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#3 Test (already passed: 3/100)\n",
      "Values: [-10, -10, -10, -4, -3, 1, 2, 3]\n",
      "Searched value: -1\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#4 Test (already passed: 4/100)\n",
      "Values: [-10, -10, -9, -9, -9, -9, -8, -8, -7, -6, -3, -2, -2, -1, 0, 1, 2, 3, 3, 4, 4, 5, 7]\n",
      "Searched value: -7\n",
      "Expected: 8\n",
      "Result: 8\n",
      "Test passed\n",
      "\n",
      "#5 Test (already passed: 5/100)\n",
      "Values: [-10, -10, -10, -8, -7, -6, -5, -3, -2, -2, -1, -1, 0, 1, 3, 5, 6, 7, 7, 8, 9, 9, 9, 10]\n",
      "Searched value: -10\n",
      "Expected: 0\n",
      "Result: 0\n",
      "Test passed\n",
      "\n",
      "#6 Test (already passed: 6/100)\n",
      "Values: [-9, -8, -6, -4, -3, 0, 5, 5, 7, 7, 9, 10, 10]\n",
      "Searched value: -10\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#7 Test (already passed: 7/100)\n",
      "Values: [-10, -9, -9, -8, -7, -7, -6, -4, -4, -3, -3, -1, 0, 1, 2, 3, 3, 6, 6, 7, 7, 8, 10, 10, 10]\n",
      "Searched value: 1\n",
      "Expected: 13\n",
      "Result: 13\n",
      "Test passed\n",
      "\n",
      "#8 Test (already passed: 8/100)\n",
      "Values: [-10, -10, -9, -2, 4, 8, 10]\n",
      "Searched value: 7\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#9 Test (already passed: 9/100)\n",
      "Values: [-10, -10, -9, -9, -9, -8, -8, -7, -6, -5, -2, 1, 1, 2, 5, 8, 8, 8, 8, 8, 9, 9, 9]\n",
      "Searched value: -3\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#10 Test (already passed: 10/100)\n",
      "Values: [-10, -9, -7, -6, -5, 5, 6, 10]\n",
      "Searched value: 9\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#11 Test (already passed: 11/100)\n",
      "Values: [-8, -3, 0, 1, 5, 5, 10]\n",
      "Searched value: 3\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#12 Test (already passed: 12/100)\n",
      "Values: [1, 4, 5, 6, 9]\n",
      "Searched value: 7\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#13 Test (already passed: 13/100)\n",
      "Values: [-3, -2, -2, 0, 2, 5, 5, 10]\n",
      "Searched value: -1\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#14 Test (already passed: 14/100)\n",
      "Values: [-9, -9, -6, -6, -1, 2, 2, 4, 6]\n",
      "Searched value: -9\n",
      "Expected: 0\n",
      "Result: 0\n",
      "Test passed\n",
      "\n",
      "#15 Test (already passed: 15/100)\n",
      "Values: [-10, -9, -5, -4, -3, -3, -2, 0, 2, 5, 5, 5, 6, 7, 10]\n",
      "Searched value: 9\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#16 Test (already passed: 16/100)\n",
      "Values: [-7, -5, -4, -1, 1, 1, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8]\n",
      "Searched value: 9\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#17 Test (already passed: 17/100)\n",
      "Values: [-6, -2, 3, 5, 7, 10]\n",
      "Searched value: -5\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#18 Test (already passed: 18/100)\n",
      "Values: [-10, -9, -9, -9, -8, -6, -4, -3, 3, 3, 4, 7, 8, 9, 10]\n",
      "Searched value: 2\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#19 Test (already passed: 19/100)\n",
      "Values: [-7, -4, -4, 0, 1, 3, 6, 7, 9]\n",
      "Searched value: 8\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#20 Test (already passed: 20/100)\n",
      "Values: [-7, -7, -6, -5, -4, -4, -3, -3, -3, -1, 1, 2, 2, 3, 3, 5, 5, 10]\n",
      "Searched value: 3\n",
      "Expected: 13\n",
      "Result: 13\n",
      "Test passed\n",
      "\n",
      "#21 Test (already passed: 21/100)\n",
      "Values: [-9, -4, -4, -3, 0, 1, 1, 1, 2, 3, 3, 4, 5, 6, 6, 8, 8]\n",
      "Searched value: -9\n",
      "Expected: 0\n",
      "Result: 0\n",
      "Test passed\n",
      "\n",
      "#22 Test (already passed: 22/100)\n",
      "Values: [-8, -4, -3, -3, 0, 3, 8, 10]\n",
      "Searched value: -8\n",
      "Expected: 0\n",
      "Result: 0\n",
      "Test passed\n",
      "\n",
      "#23 Test (already passed: 23/100)\n",
      "Values: [-9, -8, -8, -8, -7, -3, -2, 2, 3, 4, 4, 5, 5, 7]\n",
      "Searched value: 3\n",
      "Expected: 8\n",
      "Result: 8\n",
      "Test passed\n",
      "\n",
      "#24 Test (already passed: 24/100)\n",
      "Values: [-8, -6, -5, -3, -3, -2, -2, -1, -1, -1, -1, -1, 6, 6, 9, 10, 10]\n",
      "Searched value: -10\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#25 Test (already passed: 25/100)\n",
      "Values: [-6, -3, -2, 5, 6, 8, 8, 9, 10]\n",
      "Searched value: 1\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#26 Test (already passed: 26/100)\n",
      "Values: [-10, -9, -9, -8, -8, -8, -7, -6, -5, -4, -4, -3, -2, 1, 1, 2, 3, 5, 6, 6, 6, 7, 10]\n",
      "Searched value: 10\n",
      "Expected: 22\n",
      "Result: 22\n",
      "Test passed\n",
      "\n",
      "#27 Test (already passed: 27/100)\n",
      "Values: [-4, -3, -3, -2, -1, 0, 0, 6, 6, 6, 8, 9, 10]\n",
      "Searched value: 8\n",
      "Expected: 10\n",
      "Result: 10\n",
      "Test passed\n",
      "\n",
      "#28 Test (already passed: 28/100)\n",
      "Values: [-10, -10, -9, -8, -7, -6, -3, -2, 1, 2, 2, 4, 5, 5, 7, 7, 8, 9, 10]\n",
      "Searched value: 0\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#29 Test (already passed: 29/100)\n",
      "Values: [-9, -9, 3, 4, 9, 9, 10]\n",
      "Searched value: 1\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#30 Test (already passed: 30/100)\n",
      "Values: [-10, -10, -10, -9, -7, -7, -6, -6, -2, 2, 2, 10]\n",
      "Searched value: -8\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#31 Test (already passed: 31/100)\n",
      "Values: [-1, 0, 0, 0, 1, 4, 5, 5, 8]\n",
      "Searched value: -4\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#32 Test (already passed: 32/100)\n",
      "Values: [-10, -5, -3, -3, -2, -1, 2, 3, 3, 4, 4, 5, 5, 6, 6, 9]\n",
      "Searched value: -4\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#33 Test (already passed: 33/100)\n",
      "Values: [-9, -8, -8, -6, -4, -3, -2, 0, 2, 2, 5, 6]\n",
      "Searched value: -9\n",
      "Expected: 0\n",
      "Result: 0\n",
      "Test passed\n",
      "\n",
      "#34 Test (already passed: 34/100)\n",
      "Values: [-6, -5, -3, -3, 2, 2, 3, 3, 9, 9]\n",
      "Searched value: -10\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#35 Test (already passed: 35/100)\n",
      "Values: [-10, -10, -7, -5, -4, -2, 9, 9]\n",
      "Searched value: -3\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#36 Test (already passed: 36/100)\n",
      "Values: [-10, -10, -7, -5, -5, -5, -3, 1, 1, 2, 5, 5, 6, 6, 7, 8, 9, 10]\n",
      "Searched value: -10\n",
      "Expected: 0\n",
      "Result: 0\n",
      "Test passed\n",
      "\n",
      "#37 Test (already passed: 37/100)\n",
      "Values: [-10, -9, -9, -5, -5, -1, -1, -1, 2, 2, 3, 3, 3, 4, 6, 7, 7, 8]\n",
      "Searched value: -4\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#38 Test (already passed: 38/100)\n",
      "Values: [-9, -7, -5, -5, -4, -3, -2, -2, -1, 0, 1, 3, 4, 6, 9, 10]\n",
      "Searched value: 1\n",
      "Expected: 10\n",
      "Result: 10\n",
      "Test passed\n",
      "\n",
      "#39 Test (already passed: 39/100)\n",
      "Values: [-8, -5, -2, -2, -1, 0, 2, 5, 6, 7, 9]\n",
      "Searched value: 5\n",
      "Expected: 7\n",
      "Result: 7\n",
      "Test passed\n",
      "\n",
      "#40 Test (already passed: 40/100)\n",
      "Values: [-8, -8, -7, -7, -6, -3, 0, 1, 1, 2, 3, 4, 5, 5, 6, 7, 7, 7, 8, 9, 9, 10]\n",
      "Searched value: -9\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#41 Test (already passed: 41/100)\n",
      "Values: [-10, -10, -10, -4, 3, 4, 5, 6]\n",
      "Searched value: -4\n",
      "Expected: 3\n",
      "Result: 3\n",
      "Test passed\n",
      "\n",
      "#42 Test (already passed: 42/100)\n",
      "Values: [-10, -9, -5, 0, 3, 3, 5, 6, 6, 9]\n",
      "Searched value: -7\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#43 Test (already passed: 43/100)\n",
      "Values: [-10, -7, -4, 0, 3, 4, 6, 7, 8]\n",
      "Searched value: 7\n",
      "Expected: 7\n",
      "Result: 7\n",
      "Test passed\n",
      "\n",
      "#44 Test (already passed: 44/100)\n",
      "Values: [-8, -7, -5, -5, -4, -4, -4, -3, -2, -1, 0, 1, 3, 4, 5, 6, 9]\n",
      "Searched value: 0\n",
      "Expected: 10\n",
      "Result: 10\n",
      "Test passed\n",
      "\n",
      "#45 Test (already passed: 45/100)\n",
      "Values: [-10, -9, -9, -9, -8, -8, -7, -7, -5, -5, -4, -2, 0, 0, 4, 5, 6, 7, 7, 8, 8]\n",
      "Searched value: 8\n",
      "Expected: 19\n",
      "Result: 19\n",
      "Test passed\n",
      "\n",
      "#46 Test (already passed: 46/100)\n",
      "Values: [-10, -6, -5, -3, 2, 2, 4, 8]\n",
      "Searched value: -6\n",
      "Expected: 1\n",
      "Result: 1\n",
      "Test passed\n",
      "\n",
      "#47 Test (already passed: 47/100)\n",
      "Values: [-7, -6, -5, -3, -2, 1, 4, 5, 6, 10]\n",
      "Searched value: -9\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#48 Test (already passed: 48/100)\n",
      "Values: [-10, -10, -9, -7, -5, -2, 2, 2, 3, 3, 4, 8, 9]\n",
      "Searched value: -10\n",
      "Expected: 0\n",
      "Result: 0\n",
      "Test passed\n",
      "\n",
      "#49 Test (already passed: 49/100)\n",
      "Values: [-7, -5, -2, -1, -1, -1, 0, 0, 1, 1, 2, 3, 4, 5, 8, 9]\n",
      "Searched value: -8\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#50 Test (already passed: 50/100)\n",
      "Values: [-10, -7, -6, -4, -2, -2, 0, 0, 1, 2, 4, 5, 5, 6, 6, 7, 8, 10]\n",
      "Searched value: 6\n",
      "Expected: 13\n",
      "Result: 13\n",
      "Test passed\n",
      "\n",
      "#51 Test (already passed: 51/100)\n",
      "Values: [-9, -7, -5, -4, -4, -3, -2, -1, 0, 1, 1, 3, 4, 5, 6, 7, 8, 9, 10]\n",
      "Searched value: -4\n",
      "Expected: 3\n",
      "Result: 3\n",
      "Test passed\n",
      "\n",
      "#52 Test (already passed: 52/100)\n",
      "Values: [-9, -8, -6, -6, -5, -3, -2, -2, -2, -1, -1, 0, 0, 1, 2, 6, 6, 6, 7, 7]\n",
      "Searched value: -5\n",
      "Expected: 4\n",
      "Result: 4\n",
      "Test passed\n",
      "\n",
      "#53 Test (already passed: 53/100)\n",
      "Values: [-7, -6, -6, -6, -4, -3, -1, 5, 6, 6, 6, 7, 9, 10]\n",
      "Searched value: -7\n",
      "Expected: 0\n",
      "Result: 0\n",
      "Test passed\n",
      "\n",
      "#54 Test (already passed: 54/100)\n",
      "Values: [-9, -8, -7, -6, -5, -4, -4, -1, 1, 1, 4, 6, 6, 6, 9, 9]\n",
      "Searched value: -4\n",
      "Expected: 5\n",
      "Result: 5\n",
      "Test passed\n",
      "\n",
      "#55 Test (already passed: 55/100)\n",
      "Values: [-10, -10, -10, -9, -9, -6, -3, -1, 0, 4, 4, 5, 7, 7, 7, 8, 9]\n",
      "Searched value: 7\n",
      "Expected: 12\n",
      "Result: 12\n",
      "Test passed\n",
      "\n",
      "#56 Test (already passed: 56/100)\n",
      "Values: [-1, 1, 3, 4, 5, 8, 9, 9]\n",
      "Searched value: -8\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#57 Test (already passed: 57/100)\n",
      "Values: [-10, -10, -10, -8, -8, -7, -5, -4, -4, -2, -1, 1, 3, 5, 6, 6, 8, 8, 8, 8, 10]\n",
      "Searched value: -10\n",
      "Expected: 0\n",
      "Result: 0\n",
      "Test passed\n",
      "\n",
      "#58 Test (already passed: 58/100)\n",
      "Values: [-9, -7, -6, -1, 6, 6]\n",
      "Searched value: 3\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#59 Test (already passed: 59/100)\n",
      "Values: [-10, -7, -7, -6, -6, -6, -5, -5, -4, -3, 1, 2, 2, 2, 2, 4, 5, 5, 7, 7, 7, 8]\n",
      "Searched value: -2\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#60 Test (already passed: 60/100)\n",
      "Values: [-10, -9, -8, -6, -5, -3, -2, 1, 1, 2, 2, 5, 6, 8]\n",
      "Searched value: -4\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#61 Test (already passed: 61/100)\n",
      "Values: [-9, -8, -8, -5, -3, 3, 5, 9, 10, 10]\n",
      "Searched value: 5\n",
      "Expected: 6\n",
      "Result: 6\n",
      "Test passed\n",
      "\n",
      "#62 Test (already passed: 62/100)\n",
      "Values: [-9, -5, -4, -1, 0, 5, 6]\n",
      "Searched value: -4\n",
      "Expected: 2\n",
      "Result: 2\n",
      "Test passed\n",
      "\n",
      "#63 Test (already passed: 63/100)\n",
      "Values: [-7, -2, -1, 2, 10]\n",
      "Searched value: -2\n",
      "Expected: 1\n",
      "Result: 1\n",
      "Test passed\n",
      "\n",
      "#64 Test (already passed: 64/100)\n",
      "Values: [-10, -9, -8, -8, -7, -3, -3, -2, -1, -1, -1, 1, 2, 2, 3, 4, 4, 5, 7, 7, 10]\n",
      "Searched value: 4\n",
      "Expected: 15\n",
      "Result: 15\n",
      "Test passed\n",
      "\n",
      "#65 Test (already passed: 65/100)\n",
      "Values: [-10, -9, -8, -7, -6, -4, -4, -3, 2, 2, 3, 3, 5, 5, 7, 7, 7, 8, 9, 10, 10]\n",
      "Searched value: -5\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#66 Test (already passed: 66/100)\n",
      "Values: [-8, -2, -1, 0, 3, 5, 7, 9]\n",
      "Searched value: -9\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#67 Test (already passed: 67/100)\n",
      "Values: [-10, -10, -7, -7, -4, -1, 1, 5, 10]\n",
      "Searched value: 7\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#68 Test (already passed: 68/100)\n",
      "Values: [-10, -9, -8, -7, -6, -4, -3, -3, -3, 0, 1, 2, 2, 3, 3, 3, 4, 7, 7, 8, 9, 9]\n",
      "Searched value: -10\n",
      "Expected: 0\n",
      "Result: 0\n",
      "Test passed\n",
      "\n",
      "#69 Test (already passed: 69/100)\n",
      "Values: [-7, -6, -5, -5, -3, -1, 2, 9, 9]\n",
      "Searched value: 3\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#70 Test (already passed: 70/100)\n",
      "Values: [-10, -10, -9, -9, -9, -8, 0, 1, 1, 1, 2, 2, 3, 3, 5, 7]\n",
      "Searched value: -7\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#71 Test (already passed: 71/100)\n",
      "Values: [-10, -10, -9, -6, -6, -3, -2, -2, -2, -1, -1, 0, 1, 2, 2, 3, 3, 3, 5, 6, 7, 8]\n",
      "Searched value: -7\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#72 Test (already passed: 72/100)\n",
      "Values: [-10, -10, -9, -9, -9, -6, -6, -2, -2, -1, -1, -1, 0, 0, 0, 0, 0, 4, 6, 6, 8, 9, 9, 9, 10]\n",
      "Searched value: -3\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#73 Test (already passed: 73/100)\n",
      "Values: [-5, 7, 8, 8, 8]\n",
      "Searched value: -8\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#74 Test (already passed: 74/100)\n",
      "Values: [-10, -10, -9, -9, -8, -7, -6, -5, -3, -2, -1, -1, 0, 0, 1, 2, 2, 4, 4, 5, 5, 5, 9, 10]\n",
      "Searched value: -2\n",
      "Expected: 9\n",
      "Result: 9\n",
      "Test passed\n",
      "\n",
      "#75 Test (already passed: 75/100)\n",
      "Values: [-10, -10, -10, -8, -8, -7, -7, -4, -4, -4, -1, -1, 0, 1, 2, 4, 5, 5, 5, 6, 6, 8]\n",
      "Searched value: -5\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#76 Test (already passed: 76/100)\n",
      "Values: [-8, -6, -5, -3, -1, 4, 7, 10, 10]\n",
      "Searched value: -3\n",
      "Expected: 3\n",
      "Result: 3\n",
      "Test passed\n",
      "\n",
      "#77 Test (already passed: 77/100)\n",
      "Values: [-10, -10, -9, -9, -9, -7, -6, -4, -3, -2, -2, -2, -1, -1, -1, 0, 0, 2, 4, 6, 7, 8]\n",
      "Searched value: -1\n",
      "Expected: 12\n",
      "Result: 12\n",
      "Test passed\n",
      "\n",
      "#78 Test (already passed: 78/100)\n",
      "Values: [-9, -9, -8, -8, -6, -4, -1, 0, 1, 1, 3, 3, 7, 7, 7, 8, 8, 8, 9]\n",
      "Searched value: 2\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#79 Test (already passed: 79/100)\n",
      "Values: [-9, -7, -6, -3, -3, 4, 7, 8, 9]\n",
      "Searched value: -4\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#80 Test (already passed: 80/100)\n",
      "Values: [-10, -10, -8, -8, -5, -4, -2, 0, 4, 7, 9, 9, 10, 10]\n",
      "Searched value: 3\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#81 Test (already passed: 81/100)\n",
      "Values: [-8, -4, -2, 7, 8]\n",
      "Searched value: -2\n",
      "Expected: 2\n",
      "Result: 2\n",
      "Test passed\n",
      "\n",
      "#82 Test (already passed: 82/100)\n",
      "Values: [-9, -8, -8, -8, -7, -6, -6, -5, 0, 0, 1, 1, 2, 2, 2, 3, 5, 5, 6, 6, 7, 9, 9]\n",
      "Searched value: 1\n",
      "Expected: 10\n",
      "Result: 10\n",
      "Test passed\n",
      "\n",
      "#83 Test (already passed: 83/100)\n",
      "Values: [-7, -5, -1, 0, 0, 0, 1, 3, 3, 4, 5, 7, 8, 8, 9, 10]\n",
      "Searched value: -10\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#84 Test (already passed: 84/100)\n",
      "Values: [-9, -9, -6, -4, -3, -3, -2, -1, -1, 1, 3, 4, 5, 5, 7, 9]\n",
      "Searched value: -3\n",
      "Expected: 4\n",
      "Result: 4\n",
      "Test passed\n",
      "\n",
      "#85 Test (already passed: 85/100)\n",
      "Values: [-10, -9, -8, -7, -5, -2, -2, -2, 0, 0, 0, 1, 1, 2, 2, 3, 4, 6, 10]\n",
      "Searched value: 3\n",
      "Expected: 15\n",
      "Result: 15\n",
      "Test passed\n",
      "\n",
      "#86 Test (already passed: 86/100)\n",
      "Values: [-9, -9, -9, -9, -9, -8, -8, -7, -7, -6, -5, -5, -3, -1, -1, -1, 0, 1, 2, 3, 5, 5, 6, 6, 9]\n",
      "Searched value: -4\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#87 Test (already passed: 87/100)\n",
      "Values: [-7, -6, -6, -6, -5, -4, -4, -3, -2, 0, 2, 4, 9, 9, 10]\n",
      "Searched value: 8\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#88 Test (already passed: 88/100)\n",
      "Values: [-9, -6, -5, -4, -3, -1, 0, 0, 0, 1, 1, 3, 8, 9]\n",
      "Searched value: 4\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#89 Test (already passed: 89/100)\n",
      "Values: [-10, -10, -9, -7, -6, -6, -5, -3, -2, 2, 2, 3, 5, 6, 7]\n",
      "Searched value: 8\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#90 Test (already passed: 90/100)\n",
      "Values: [-7, -7, -7, -6, -4, -4, -4, -3, -1, 1, 1, 3, 6, 6, 8, 8, 9, 9, 9, 10, 10]\n",
      "Searched value: 0\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#91 Test (already passed: 91/100)\n",
      "Values: [-7, -7, -3, 4, 4, 4, 5, 9]\n",
      "Searched value: -8\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#92 Test (already passed: 92/100)\n",
      "Values: [-8, -4, -2, -2, -2, -1, 0, 1, 2, 3, 7, 8, 9, 9]\n",
      "Searched value: 2\n",
      "Expected: 8\n",
      "Result: 8\n",
      "Test passed\n",
      "\n",
      "#93 Test (already passed: 93/100)\n",
      "Values: [-8, -8, -6, -5, -4, -3, -2, -2, -1, 7, 8, 8, 10]\n",
      "Searched value: -4\n",
      "Expected: 4\n",
      "Result: 4\n",
      "Test passed\n",
      "\n",
      "#94 Test (already passed: 94/100)\n",
      "Values: [-10, -8, -7, -6, -5, -5, 3, 5, 6, 8]\n",
      "Searched value: -7\n",
      "Expected: 2\n",
      "Result: 2\n",
      "Test passed\n",
      "\n",
      "#95 Test (already passed: 95/100)\n",
      "Values: [-9, 0, 0, 2, 6, 6, 8, 8, 8]\n",
      "Searched value: 2\n",
      "Expected: 3\n",
      "Result: 3\n",
      "Test passed\n",
      "\n",
      "#96 Test (already passed: 96/100)\n",
      "Values: [-9, -4, -3, -3, -2, -1, -1, -1, 0, 3, 4, 4, 4, 5, 6, 7, 7]\n",
      "Searched value: 8\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#97 Test (already passed: 97/100)\n",
      "Values: [-3, 0, 2, 2, 3, 4]\n",
      "Searched value: 1\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#98 Test (already passed: 98/100)\n",
      "Values: [-9, -7, -6, -5, -2, -1, -1, 0, 0, 0, 2, 3]\n",
      "Searched value: 7\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#99 Test (already passed: 99/100)\n",
      "Values: [-9, -6, -6, -6, -3, -3, -2, 2, 5, 7, 7, 8, 10]\n",
      "Searched value: -2\n",
      "Expected: 6\n",
      "Result: 6\n",
      "Test passed\n",
      "\n",
      "#100 Test (already passed: 100/100)\n",
      "Values: [-10, -10, -10, -9, -7, -6, -4, -4, 0, 0, 1, 3, 6, 6, 7, 10]\n",
      "Searched value: 2\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "Total passed: 100/100\n",
      "An algorithm is correct\n"
     ]
    }
   ],
   "source": [
    "test_find(find_first, reps=100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### (Dodatkowo) Implementacja algorytmu, który zwraca indeks ostatniej przekazanej do wyszukania wartości"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_last(arr, val):\n",
    "    i = 0\n",
    "    j = len(arr) - 1\n",
    "    while i <= j:\n",
    "        center_idx = (i + j) // 2\n",
    "        if val < arr[center_idx]:\n",
    "            j = center_idx - 1\n",
    "        else:\n",
    "            i = center_idx + 1\n",
    "    return j if j < len(arr) and arr[j] == val else None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Implementacja funkcji testującej prawidłowość algorytmu (nie jest częścią zadania)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def test_find(fn, *, reps=20):\n",
    "    passed = 0\n",
    "    for i in range(reps):\n",
    "        values = sorted(random.randint(-10, 10) for _ in range(random.randint(5, 25)))\n",
    "        searched = random.randint(-10, 10)\n",
    "        result = fn(values, searched)\n",
    "        expected = None\n",
    "        found = False\n",
    "        for i in range(len(values)):\n",
    "            if searched == values[i]:\n",
    "                expected = i\n",
    "                found = True\n",
    "            elif found:\n",
    "                break\n",
    "        is_correct = expected == result\n",
    "        print(f'#{i+1} Test (already passed: {passed}/{reps})')\n",
    "        print('Values:', values)\n",
    "        print('Searched value:', searched)\n",
    "        print('Expected:', expected)\n",
    "        print('Result:', result)\n",
    "        print(f'Test {\"passed\" if is_correct else \"failed\"}')\n",
    "        print()\n",
    "        passed += is_correct\n",
    "    print(f'Total passed: {passed}/{reps}')\n",
    "    print(f'An algorithm is {\"correct\" if passed == reps else \"wrong\"}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Przykładowy test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#4 Test (already passed: 0/100)\n",
      "Values: [-10, -9, -4, -3, -2, -1, -1, 0, 0, 0, 2, 6]\n",
      "Searched value: -4\n",
      "Expected: 2\n",
      "Result: 2\n",
      "Test passed\n",
      "\n",
      "#23 Test (already passed: 1/100)\n",
      "Values: [-8, -8, -7, -6, -5, -5, -2, -2, -1, -1, 1, 1, 1, 1, 3, 5, 6, 6, 7, 7, 8, 8, 8]\n",
      "Searched value: 9\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#22 Test (already passed: 2/100)\n",
      "Values: [-10, -10, -10, -8, -8, -7, -7, -7, -6, -5, -5, -3, -3, -2, 0, 3, 5, 6, 6, 7, 7, 9]\n",
      "Searched value: 7\n",
      "Expected: 20\n",
      "Result: 20\n",
      "Test passed\n",
      "\n",
      "#19 Test (already passed: 3/100)\n",
      "Values: [-10, -9, -9, -9, -6, -6, -5, -5, -1, -1, 1, 3, 3, 3, 4, 5, 5, 6, 7, 8, 9, 9, 10, 10, 10]\n",
      "Searched value: 6\n",
      "Expected: 17\n",
      "Result: 17\n",
      "Test passed\n",
      "\n",
      "#13 Test (already passed: 4/100)\n",
      "Values: [-10, -10, -10, -9, -7, -7, -6, -5, -4, -2, 0, 0, 2, 3, 3, 4, 7, 7, 7, 10]\n",
      "Searched value: 0\n",
      "Expected: 11\n",
      "Result: 11\n",
      "Test passed\n",
      "\n",
      "#5 Test (already passed: 5/100)\n",
      "Values: [-4, -1, 0, 4, 9]\n",
      "Searched value: 2\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#13 Test (already passed: 6/100)\n",
      "Values: [-9, -8, -8, -7, -5, -4, -4, -3, -2, -2, -2, -1, 0, 1, 2, 3, 4, 5, 7, 8, 9]\n",
      "Searched value: -1\n",
      "Expected: 11\n",
      "Result: 11\n",
      "Test passed\n",
      "\n",
      "#8 Test (already passed: 7/100)\n",
      "Values: [-10, -7, -7, -7, -5, -5, -4, -2, -2, -1, -1, 1, 4, 4, 4, 4, 5, 6, 6, 9]\n",
      "Searched value: -4\n",
      "Expected: 6\n",
      "Result: 6\n",
      "Test passed\n",
      "\n",
      "#15 Test (already passed: 8/100)\n",
      "Values: [-8, -7, -5, -5, -4, -1, 0, 1, 3, 4, 4, 4, 4, 8, 10]\n",
      "Searched value: 6\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#15 Test (already passed: 9/100)\n",
      "Values: [-10, -7, -5, -5, -4, -4, -4, -2, -2, -1, 3, 4, 5, 8, 8]\n",
      "Searched value: -3\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#9 Test (already passed: 10/100)\n",
      "Values: [-10, -8, -7, -2, -1, 3, 3, 4, 8]\n",
      "Searched value: 2\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#16 Test (already passed: 11/100)\n",
      "Values: [-10, -8, -8, -6, -2, -1, 0, 1, 1, 2, 2, 3, 5, 6, 6, 7]\n",
      "Searched value: -9\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#9 Test (already passed: 12/100)\n",
      "Values: [-10, -9, -8, -7, -6, -3, -3, -2, -1, 0, 0, 1, 1, 2, 4, 4, 4, 5, 6, 6, 7, 9, 10]\n",
      "Searched value: -2\n",
      "Expected: 7\n",
      "Result: 7\n",
      "Test passed\n",
      "\n",
      "#14 Test (already passed: 13/100)\n",
      "Values: [-10, -8, -8, -2, -2, 1, 3, 3, 3, 4, 8, 8, 9, 10]\n",
      "Searched value: -5\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#14 Test (already passed: 14/100)\n",
      "Values: [-9, -9, -8, -5, -3, -2, -2, 3, 3, 4, 4, 7, 7, 9]\n",
      "Searched value: 0\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#13 Test (already passed: 15/100)\n",
      "Values: [-9, -8, -6, -3, -3, -2, -1, 4, 5, 5, 8, 8, 10]\n",
      "Searched value: 3\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#19 Test (already passed: 16/100)\n",
      "Values: [-10, -10, -10, -9, -9, -6, -6, -3, -2, -1, 1, 4, 6, 6, 7, 8, 9, 10, 10]\n",
      "Searched value: 10\n",
      "Expected: 18\n",
      "Result: 18\n",
      "Test passed\n",
      "\n",
      "#5 Test (already passed: 17/100)\n",
      "Values: [-8, -2, 5, 6, 9]\n",
      "Searched value: 6\n",
      "Expected: 3\n",
      "Result: 3\n",
      "Test passed\n",
      "\n",
      "#25 Test (already passed: 18/100)\n",
      "Values: [-10, -9, -8, -8, -8, -6, -6, -4, -4, -4, -2, -1, -1, 0, 0, 0, 1, 1, 2, 5, 5, 9, 10, 10, 10]\n",
      "Searched value: 7\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#22 Test (already passed: 19/100)\n",
      "Values: [-10, -9, -9, -9, -8, -7, -4, -3, -2, -1, 0, 2, 2, 3, 4, 5, 6, 8, 8, 8, 9, 10]\n",
      "Searched value: 9\n",
      "Expected: 20\n",
      "Result: 20\n",
      "Test passed\n",
      "\n",
      "#15 Test (already passed: 20/100)\n",
      "Values: [-10, -10, -10, -9, -9, -8, -7, -5, -4, -4, 3, 5, 7, 7, 8, 9, 9, 10, 10]\n",
      "Searched value: 7\n",
      "Expected: 13\n",
      "Result: 13\n",
      "Test passed\n",
      "\n",
      "#11 Test (already passed: 21/100)\n",
      "Values: [-10, -8, -7, -6, -5, -5, -5, -4, -1, 2, 2]\n",
      "Searched value: 4\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#8 Test (already passed: 22/100)\n",
      "Values: [-7, -5, -4, -4, 0, 0, 6, 7]\n",
      "Searched value: -1\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#6 Test (already passed: 23/100)\n",
      "Values: [-6, -5, -4, -3, -2, -1, 1, 2, 5, 6, 6, 7, 7, 7, 8, 9]\n",
      "Searched value: -2\n",
      "Expected: 4\n",
      "Result: 4\n",
      "Test passed\n",
      "\n",
      "#19 Test (already passed: 24/100)\n",
      "Values: [-10, -10, -10, -9, -7, -6, -4, -3, -3, -1, -1, -1, 0, 5, 5, 7, 7, 8, 9, 9, 9]\n",
      "Searched value: 8\n",
      "Expected: 17\n",
      "Result: 17\n",
      "Test passed\n",
      "\n",
      "#21 Test (already passed: 25/100)\n",
      "Values: [-10, -8, -6, -6, -5, -3, -2, -2, -2, -1, -1, -1, 3, 4, 4, 4, 4, 5, 7, 10, 10]\n",
      "Searched value: 6\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#2 Test (already passed: 26/100)\n",
      "Values: [-9, -8, -8, -3, -2, -2, -1, -1, -1, -1, 0, 2, 4, 4, 5, 5, 7, 7, 8, 9, 10, 10]\n",
      "Searched value: -9\n",
      "Expected: 0\n",
      "Result: 0\n",
      "Test passed\n",
      "\n",
      "#19 Test (already passed: 27/100)\n",
      "Values: [-10, -10, -9, -9, -7, -6, -5, -3, -2, -2, 0, 1, 2, 3, 4, 8, 9, 9, 10]\n",
      "Searched value: -1\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#15 Test (already passed: 28/100)\n",
      "Values: [-10, -5, -4, -3, 1, 2, 3, 4, 4, 4, 5, 7, 7, 8, 10]\n",
      "Searched value: -2\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#22 Test (already passed: 29/100)\n",
      "Values: [-10, -10, -9, -8, -8, -8, -5, -5, -3, -2, -1, 0, 0, 1, 4, 4, 4, 5, 5, 7, 8, 10]\n",
      "Searched value: 8\n",
      "Expected: 20\n",
      "Result: 20\n",
      "Test passed\n",
      "\n",
      "#10 Test (already passed: 30/100)\n",
      "Values: [-10, -8, -6, 2, 3, 3, 4, 4, 5, 10]\n",
      "Searched value: 5\n",
      "Expected: 8\n",
      "Result: 8\n",
      "Test passed\n",
      "\n",
      "#6 Test (already passed: 31/100)\n",
      "Values: [-1, 1, 1, 8, 9, 9]\n",
      "Searched value: -9\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#6 Test (already passed: 32/100)\n",
      "Values: [-9, -8, -7, -7, -2, -1, -1, 0, 2, 6, 7, 7]\n",
      "Searched value: -2\n",
      "Expected: 4\n",
      "Result: 4\n",
      "Test passed\n",
      "\n",
      "#6 Test (already passed: 33/100)\n",
      "Values: [-5, -4, -1, 6, 8, 9]\n",
      "Searched value: -10\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#15 Test (already passed: 34/100)\n",
      "Values: [-9, -9, -8, -7, -7, -6, -5, -3, -3, -1, -1, 7, 7, 9, 10]\n",
      "Searched value: 8\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#8 Test (already passed: 35/100)\n",
      "Values: [-8, -1, -1, 1, 2, 5, 5, 7]\n",
      "Searched value: 9\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#17 Test (already passed: 36/100)\n",
      "Values: [-9, -7, -5, -5, -4, -3, -2, -2, -2, 0, 1, 1, 2, 4, 5, 6, 10]\n",
      "Searched value: -8\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#5 Test (already passed: 37/100)\n",
      "Values: [-5, -5, 4, 6, 7]\n",
      "Searched value: -4\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#20 Test (already passed: 38/100)\n",
      "Values: [-9, -8, -8, -8, -7, -7, -6, -3, -3, -2, -2, 2, 2, 5, 6, 6, 7, 10, 10, 10]\n",
      "Searched value: -5\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#7 Test (already passed: 39/100)\n",
      "Values: [-8, -6, -5, -4, -4, -4, -3, -3, -1, 0, 0, 0, 5, 7, 10]\n",
      "Searched value: -4\n",
      "Expected: 5\n",
      "Result: 5\n",
      "Test passed\n",
      "\n",
      "#12 Test (already passed: 40/100)\n",
      "Values: [-9, -8, -5, -2, -2, -1, 3, 5, 7, 8, 9, 9]\n",
      "Searched value: -6\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#16 Test (already passed: 41/100)\n",
      "Values: [-8, -6, -5, -4, -3, -3, -3, -2, -1, 1, 1, 1, 2, 7, 8, 9]\n",
      "Searched value: -7\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#16 Test (already passed: 42/100)\n",
      "Values: [-10, -9, -7, -7, -4, -3, 1, 2, 3, 3, 5, 5, 5, 7, 8, 10]\n",
      "Searched value: 0\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#21 Test (already passed: 43/100)\n",
      "Values: [-10, -8, -6, -6, -6, -6, -5, -4, -2, -2, 0, 2, 2, 3, 3, 4, 6, 6, 7, 7, 8, 8, 9, 10, 10]\n",
      "Searched value: 7\n",
      "Expected: 19\n",
      "Result: 19\n",
      "Test passed\n",
      "\n",
      "#19 Test (already passed: 44/100)\n",
      "Values: [-10, -10, -9, -9, -6, -5, -4, -4, -3, -1, 0, 1, 3, 4, 6, 9, 10, 10, 10]\n",
      "Searched value: -8\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#21 Test (already passed: 45/100)\n",
      "Values: [-10, -10, -9, -8, -7, -6, -6, -5, -4, -3, -1, 2, 2, 3, 3, 5, 6, 7, 7, 7, 9]\n",
      "Searched value: 8\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#21 Test (already passed: 46/100)\n",
      "Values: [-10, -10, -9, -9, -8, -8, -7, -7, -6, -3, -2, -1, -1, 0, 1, 3, 4, 5, 6, 8, 10, 10, 10, 10]\n",
      "Searched value: 8\n",
      "Expected: 19\n",
      "Result: 19\n",
      "Test passed\n",
      "\n",
      "#17 Test (already passed: 47/100)\n",
      "Values: [-10, -10, -10, -7, -5, -4, -3, -3, -2, -1, 2, 3, 3, 5, 5, 8, 8]\n",
      "Searched value: 1\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#12 Test (already passed: 48/100)\n",
      "Values: [-10, -9, -9, -7, -2, -2, -1, 0, 5, 9, 9, 10]\n",
      "Searched value: 9\n",
      "Expected: 10\n",
      "Result: 10\n",
      "Test passed\n",
      "\n",
      "#2 Test (already passed: 49/100)\n",
      "Values: [-7, -2, 0, 5, 6]\n",
      "Searched value: -7\n",
      "Expected: 0\n",
      "Result: 0\n",
      "Test passed\n",
      "\n",
      "#13 Test (already passed: 50/100)\n",
      "Values: [-9, -5, -1, -1, 0, 1, 1, 4, 5, 8, 8, 8, 9]\n",
      "Searched value: 9\n",
      "Expected: 12\n",
      "Result: 12\n",
      "Test passed\n",
      "\n",
      "#18 Test (already passed: 51/100)\n",
      "Values: [-7, -7, -5, -4, -2, -1, -1, 0, 1, 2, 3, 3, 5, 7, 8, 8, 10, 10]\n",
      "Searched value: -6\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#10 Test (already passed: 52/100)\n",
      "Values: [-10, -9, -9, -9, -9, -7, -7, -6, -6, -5, -5, -4, -4, -1, 0, 1, 2, 2, 5, 6, 6, 9, 9, 10]\n",
      "Searched value: -6\n",
      "Expected: 8\n",
      "Result: 8\n",
      "Test passed\n",
      "\n",
      "#24 Test (already passed: 53/100)\n",
      "Values: [-10, -10, -10, -9, -9, -6, -4, -4, -3, -3, -2, -2, 2, 2, 2, 2, 4, 6, 6, 6, 8, 8, 8, 9, 10]\n",
      "Searched value: 8\n",
      "Expected: 22\n",
      "Result: 22\n",
      "Test passed\n",
      "\n",
      "#19 Test (already passed: 54/100)\n",
      "Values: [-9, -9, -8, -7, -7, -6, -2, -2, -2, 2, 2, 3, 4, 5, 7, 9, 10, 10, 10]\n",
      "Searched value: 6\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#8 Test (already passed: 55/100)\n",
      "Values: [-3, 0, 1, 2, 3, 4, 6, 10]\n",
      "Searched value: 5\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#7 Test (already passed: 56/100)\n",
      "Values: [-6, -6, -4, 2, 4, 5, 6]\n",
      "Searched value: 10\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#24 Test (already passed: 57/100)\n",
      "Values: [-10, -8, -8, -6, -5, -3, -2, -2, -1, 0, 0, 0, 0, 1, 1, 1, 3, 5, 5, 5, 7, 7, 7, 9]\n",
      "Searched value: -9\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#6 Test (already passed: 58/100)\n",
      "Values: [-8, -3, 2, 3, 8, 9]\n",
      "Searched value: 5\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#4 Test (already passed: 59/100)\n",
      "Values: [-5, -2, -1, 0, 5, 10]\n",
      "Searched value: -1\n",
      "Expected: 2\n",
      "Result: 2\n",
      "Test passed\n",
      "\n",
      "#6 Test (already passed: 60/100)\n",
      "Values: [-9, -9, -6, -3, 4, 5]\n",
      "Searched value: 6\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#19 Test (already passed: 61/100)\n",
      "Values: [-10, -10, -10, -10, -9, -8, -8, -7, -7, -6, -5, -5, -5, -3, -2, -2, -1, 0, 4, 5, 7, 7, 8, 9, 10]\n",
      "Searched value: 0\n",
      "Expected: 17\n",
      "Result: 17\n",
      "Test passed\n",
      "\n",
      "#25 Test (already passed: 62/100)\n",
      "Values: [-6, -5, -4, -4, -4, -3, -3, -3, -3, -3, -2, -1, 2, 2, 2, 3, 4, 4, 4, 4, 4, 5, 8, 9, 10]\n",
      "Searched value: -9\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#12 Test (already passed: 63/100)\n",
      "Values: [-10, -8, -8, -5, -5, -2, -2, -1, 0, 4, 8, 9]\n",
      "Searched value: 7\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#9 Test (already passed: 64/100)\n",
      "Values: [-6, -4, -3, -1, 4, 6, 8, 9, 10]\n",
      "Searched value: -2\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#7 Test (already passed: 65/100)\n",
      "Values: [-10, -7, -7, -5, 0, 3, 6]\n",
      "Searched value: -2\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#16 Test (already passed: 66/100)\n",
      "Values: [-8, -8, -8, -5, -4, -3, -1, -1, 0, 2, 2, 3, 5, 5, 6, 9]\n",
      "Searched value: 6\n",
      "Expected: 14\n",
      "Result: 14\n",
      "Test passed\n",
      "\n",
      "#15 Test (already passed: 67/100)\n",
      "Values: [-9, -8, -8, -7, -3, -3, -2, 1, 2, 2, 3, 3, 5, 5, 10]\n",
      "Searched value: -5\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#18 Test (already passed: 68/100)\n",
      "Values: [-9, -8, -8, -7, -6, -6, -5, -5, -5, -1, 0, 1, 1, 3, 3, 3, 6, 8]\n",
      "Searched value: 2\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#12 Test (already passed: 69/100)\n",
      "Values: [-10, -7, -3, -3, 1, 2, 6, 8, 9, 9, 10, 10]\n",
      "Searched value: -1\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#13 Test (already passed: 70/100)\n",
      "Values: [-9, -8, -7, -7, -6, -5, -5, -4, -1, 3, 5, 7, 8]\n",
      "Searched value: 4\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#19 Test (already passed: 71/100)\n",
      "Values: [-10, -10, -10, -9, -9, -9, -7, -6, -5, -3, -3, -2, 0, 0, 0, 0, 0, 1, 2, 3, 4, 4, 5, 8, 10]\n",
      "Searched value: 1\n",
      "Expected: 17\n",
      "Result: 17\n",
      "Test passed\n",
      "\n",
      "#6 Test (already passed: 72/100)\n",
      "Values: [-10, -10, -10, -6, -6, -5, -4, -3, -2, -1, 0, 1, 1, 2, 2, 3, 3, 3, 5, 5, 8, 8, 9, 9]\n",
      "Searched value: -6\n",
      "Expected: 4\n",
      "Result: 4\n",
      "Test passed\n",
      "\n",
      "#6 Test (already passed: 73/100)\n",
      "Values: [-5, -3, -3, 1, 5, 8]\n",
      "Searched value: 3\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#5 Test (already passed: 74/100)\n",
      "Values: [-8, -6, -2, 0, 5]\n",
      "Searched value: 9\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#23 Test (already passed: 75/100)\n",
      "Values: [-10, -9, -8, -6, -5, -2, -1, -1, -1, 0, 0, 0, 0, 1, 2, 2, 2, 4, 5, 6, 7, 9, 9]\n",
      "Searched value: -3\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#21 Test (already passed: 76/100)\n",
      "Values: [-9, -8, -6, -5, -5, -4, -3, -3, -2, -1, 2, 3, 4, 4, 7, 7, 8, 8, 9, 9, 9]\n",
      "Searched value: 1\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#11 Test (already passed: 77/100)\n",
      "Values: [-10, -9, -7, -7, -5, -5, 0, 2, 3, 8, 9, 10, 10, 10]\n",
      "Searched value: 8\n",
      "Expected: 9\n",
      "Result: 9\n",
      "Test passed\n",
      "\n",
      "#17 Test (already passed: 78/100)\n",
      "Values: [-9, -9, -9, -9, -5, -5, -4, 0, 1, 1, 2, 4, 4, 5, 5, 8, 10]\n",
      "Searched value: -8\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#9 Test (already passed: 79/100)\n",
      "Values: [-10, -10, -9, -7, -6, -5, -4, -4, -3, -3, -3, -2, -2, -2, 0, 1, 2, 3, 3, 4, 5, 7, 9, 10]\n",
      "Searched value: -4\n",
      "Expected: 7\n",
      "Result: 7\n",
      "Test passed\n",
      "\n",
      "#12 Test (already passed: 80/100)\n",
      "Values: [-8, -8, -8, -6, -6, -4, -1, -1, 0, 0, 1, 2, 2, 3, 3, 3, 5, 5, 7, 7, 8, 8, 10]\n",
      "Searched value: 1\n",
      "Expected: 10\n",
      "Result: 10\n",
      "Test passed\n",
      "\n",
      "#8 Test (already passed: 81/100)\n",
      "Values: [-10, -9, -7, -5, -5, -5, -5, -3, -2, -2, 1, 1, 1, 2, 4, 5, 5, 6, 6, 7, 7, 8, 10]\n",
      "Searched value: -5\n",
      "Expected: 6\n",
      "Result: 6\n",
      "Test passed\n",
      "\n",
      "#14 Test (already passed: 82/100)\n",
      "Values: [-10, -6, -6, -6, -5, -4, -4, -2, 1, 4, 5, 5, 6, 8]\n",
      "Searched value: -8\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#25 Test (already passed: 83/100)\n",
      "Values: [-10, -10, -10, -8, -8, -7, -6, -5, -5, -5, -5, -3, -3, -2, -2, -1, -1, 0, 1, 5, 7, 8, 9, 9, 10]\n",
      "Searched value: 4\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#7 Test (already passed: 84/100)\n",
      "Values: [-10, -2, 4, 4, 8, 8, 9]\n",
      "Searched value: -3\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#22 Test (already passed: 85/100)\n",
      "Values: [-10, -10, -9, -8, -8, -8, -7, -5, -4, -4, -3, -2, -1, -1, -1, 0, 1, 2, 6, 7, 9, 10, 10]\n",
      "Searched value: 9\n",
      "Expected: 20\n",
      "Result: 20\n",
      "Test passed\n",
      "\n",
      "#7 Test (already passed: 86/100)\n",
      "Values: [-5, -3, -3, 2, 8, 8, 9]\n",
      "Searched value: 3\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#5 Test (already passed: 87/100)\n",
      "Values: [-9, -9, -9, -8, -7, -7, -7, -2, -1, 0, 1, 2, 2, 2, 3, 5, 7, 7]\n",
      "Searched value: -8\n",
      "Expected: 3\n",
      "Result: 3\n",
      "Test passed\n",
      "\n",
      "#17 Test (already passed: 88/100)\n",
      "Values: [-9, -6, -4, -4, -3, -3, -2, -2, -2, 2, 3, 4, 5, 5, 6, 7, 9]\n",
      "Searched value: -10\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#18 Test (already passed: 89/100)\n",
      "Values: [-10, -10, -10, -10, -8, -8, -7, -5, -5, -4, -3, -3, 1, 3, 7, 10, 10, 10]\n",
      "Searched value: -1\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#19 Test (already passed: 90/100)\n",
      "Values: [-9, -8, -7, -7, -6, -6, -6, -6, -4, -2, 1, 1, 2, 4, 4, 6, 7, 9, 10]\n",
      "Searched value: 0\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#10 Test (already passed: 91/100)\n",
      "Values: [-5, -5, -3, -2, -1, 4, 6, 6, 6, 7]\n",
      "Searched value: -9\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#6 Test (already passed: 92/100)\n",
      "Values: [-5, -5, -3, -3, 2, 8]\n",
      "Searched value: -7\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#10 Test (already passed: 93/100)\n",
      "Values: [-10, -8, -7, -6, -5, 0, 1, 4, 4, 5]\n",
      "Searched value: 5\n",
      "Expected: 9\n",
      "Result: 9\n",
      "Test passed\n",
      "\n",
      "#10 Test (already passed: 94/100)\n",
      "Values: [-10, -9, -4, -3, 3, 4, 4, 5, 9, 9]\n",
      "Searched value: -5\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#5 Test (already passed: 95/100)\n",
      "Values: [-8, 2, 6, 6, 7]\n",
      "Searched value: -9\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#14 Test (already passed: 96/100)\n",
      "Values: [-9, -8, -7, -6, -5, -3, -1, 2, 3, 4, 6, 7, 8, 8]\n",
      "Searched value: -2\n",
      "Expected: None\n",
      "Result: None\n",
      "Test passed\n",
      "\n",
      "#5 Test (already passed: 97/100)\n",
      "Values: [-9, -6, -2, -1, 0, 3, 5, 7, 9]\n",
      "Searched value: -1\n",
      "Expected: 3\n",
      "Result: 3\n",
      "Test passed\n",
      "\n",
      "#4 Test (already passed: 98/100)\n",
      "Values: [-9, -8, -8, -7, -7, -5, -5, -3, -1, 0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 6, 6, 8, 8, 9, 10]\n",
      "Searched value: -8\n",
      "Expected: 2\n",
      "Result: 2\n",
      "Test passed\n",
      "\n",
      "#11 Test (already passed: 99/100)\n",
      "Values: [-8, -8, -7, -7, -6, 1, 1, 1, 3, 4, 6, 8, 9]\n",
      "Searched value: 4\n",
      "Expected: 9\n",
      "Result: 9\n",
      "Test passed\n",
      "\n",
      "Total passed: 100/100\n",
      "An algorithm is correct\n"
     ]
    }
   ],
   "source": [
    "test_find(find_last, reps=100)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}